package com.zj;

/**
 * 编辑距离
 */
public class EditDistance {
    /**
     * 计算两个字符串的编辑距离   计算从word1变为word2要编辑几次==>编辑距离
     * @param word1 字符串1
     * @param word2 字符串2
     * @return 编辑距离
     */
    public static int calculate(String word1, String word2) {
//       int length1=word1.length();
//       int length2=word2.length();
//       //初始化一个数组
//        int[][]dp=new int[length1+1][length2+1];
//        //初始化第一行
//        for (int j = 0; j < length2+1; j++) {
//            dp[0][j]=j;
//        }
//        //初始化第一列
//        for (int i = 0; i < length1+1; i++) {
//            dp[i][0]=i;
//        }
//        //给数组添加值
//        for (int i = 1; i <length1+1 ; i++) {
//            for (int j=1;j<length2+1;j++){
//                if(word1.charAt(i-1)==word2.charAt(j-1)){
//                    dp[i][j]=dp[i-1][j-1];
//                }else{
//                    //无论增加，删除，减少，操作步骤+1
//                    int add=dp[i][j-1]+1;
//                    int delete=dp[i-1][j]+1;
//                    int update=dp[i-1][j-1]+1;
//                    dp[i][j]=Math.min(Math.min(add,delete),update);
//                }
//            }
//
//        }
//        return dp[length1][length2];
//    }

        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0) {
                    dp[i][j] = j;
                } else if (j == 0) {
                    dp[i][j] = i;
                } else {
                    dp[i][j] = Math.min(
                            Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1),
                            dp[i - 1][j - 1] + (word1.charAt(i - 1) == word2.charAt(j - 1) ? 0 : 1)
                    );
                }
            }
        }
        return dp[m][n];
    }
}
